package leetcode.day_2020_11_16_11_22;

import java.util.HashMap;
import java.util.Map;

public class L_28 {
    public static void main(String[] args) {
        String haystack = "mississippi";
        String needle = "issippi";
        System.out.println(strStr2(haystack, needle));
    }

    /**
     * 暴力匹配法1
     * @param haystack 目标字符串
     * @param needle 模式串
     * @return
     */
    public static int strStr(String haystack, String needle) {
        if(needle.length() == 0)
            return 0;
        // 模式串长度大于目标字符串，返回-1
        if(needle.length() > haystack.length())
            return -1;
        // 转为字符数组
        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        // 开始匹配
        for(int i=0; i<haystackArr.length; i++) {
            // 记录匹配起始位置
            int index = i;
            for(int j=0; j<needleArr.length; j++) {
                if(needleArr[j] != haystackArr[index]) {
                    break;
                }
                // 每次比较后，判断j是否达到模式串的长度，等于说明
                // 找到了匹配的字符串
                if(j == needleArr.length-1)
                    return i;
                // 如果index大于等于目标字符串的长度，说明匹配失败
                index = index +1;
                if(index >= haystackArr.length)
                    return -1;
            }
        }
        return -1;
    }

    public static int strStr2(String haystack, String needle) {
        if(needle.length() == 0)
            return 0;
        // 模式串长度大于目标字符串，返回-1
        if(needle.length() > haystack.length())
            return -1;
        // 转为字符数组
        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        // 开始匹配
        for(int i=0; i<=haystackArr.length-needleArr.length; i++) {
            int j;
            for(j=0; j<needleArr.length; j++) {
                if(needleArr[j] != haystackArr[i+j])
                    break;
            }
            if(j == needleArr.length)
                return i;
        }
        return -1;
    }
    /**
     * KMP 匹配机制
     * @param haystack
     * @param needle
     */
    public static int strStr3(String haystack, String needle) {
        if(needle.length() == 0)
            return 0;
        // 模式串长度大于目标字符串，返回-1
        if(needle.length() > haystack.length())
            return -1;
        // 转为字符数组
        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        int haystackL = haystackArr.length;
        int needleL = needleArr.length;
        // 建立偏移表
        Map<Character, Integer> mapDict = new HashMap<>();
        return 0;
    }
}
